package com.fyl.leetcode.sort;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author:fyl
 * @date 2021/4/28 16:06
 * @Modified By:
 * @Modified Date:
 * @Description:
 *  按照字符出现次数对字符串排序
 */
public class SortCharactersByFrequency {
    public static String frequencySort(String s) {
        //储存各个字符的出现频率
        Map<Character, Integer> frequency = new HashMap<>();
        for (char c : s.toCharArray()) {
            frequency.put(c, frequency.getOrDefault(c, 0) + 1);
        }
        //将字母按出现频率放入桶中
        List<Character>[] bucket = new List[s.length() + 1];
        for (Character key : frequency.keySet()) {
            int num = frequency.get(key);
            if (bucket[num] == null) {
                bucket[num] = new ArrayList<>();
            }
            bucket[num].add(key);
        }

        StringBuilder result = new StringBuilder();
        for (int i = bucket.length - 1; i >= 0; i--) {
            if (bucket[i] == null) continue;
            //可能有多字母的出现次数相同所以需要遍历bucket[i]的所有节点
            for (Character s1 : bucket[i]) {
                for (int j = 0; j < i; j++) {
                    result.append(s1);
                }
            }

        }

        return result.toString();
    }

    public static void main(String[] args) {
        String s = "treeeecc";
        System.out.println(SortCharactersByFrequency.frequencySort(s));
    }
}
